#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//void _MergeSort(int* a, int* tmp, int begin, int end)
//{
//	// 递归终止条件：如果开始索引大于或等于结束索引，说明子数组长度为0或1，无需排序，直接返回
//	if (begin >= end)
//		return;
//
//	// 计算中间索引mid
//	int mid = (begin + end) / 2;
//
//	// 递归排序左半部分
//	_MergeSort(a, tmp, begin, mid);
//	// 递归排序右半部分
//	_MergeSort(a, tmp, mid + 1, end);
//
//	// 以下是合并两个已排序的子数组的逻辑
//
//	// 初始化左右子数组的起始和结束索引
//	int begin1 = begin;
//	int end1 = mid;
//	int begin2 = mid + 1;
//	int end2 = end;
//
//	// 初始化辅助数组tmp的索引
//	int index = begin;
//
//	// 合并两个子数组，直到其中一个子数组全部合并完
//	while (begin1 <= end1 && begin2 <= end2)
//	{
//		// 如果左子数组的当前元素小于右子数组的当前元素，则将左子树的当前元素复制到辅助数组中
//		if (a[begin1] < a[begin2])
//		{
//			tmp[index++] = a[begin1++];
//		}
//		// 否则，将右子数组的当前元素复制到辅助数组tmp中
//		else
//		{
//			tmp[index++] = a[begin2++];
//		}
//	}
//
//	// 如果左子数组还有剩余元素，将其全部复制到辅助数组中
//	while (begin1 <= end1)
//	{
//		tmp[index++] = a[begin1++];
//	}
//
//	// 如果右子数组还有剩余元素，将其全部复制到辅助数组中
//	while (begin2 <= end2)
//	{
//		tmp[index++] = a[begin2++];
//	}
//
//	// 将辅助数组tmp中已排序的元素复制回原数组
//	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
//}
////开辟tmp数组
//void MergeSort(int* a, int n)
//{
//	int* tmp = (int*)malloc(sizeof(int) * n);
//	if (tmp == NULL)
//	{
//		perror("malloc failed");
//		exit(-1);
//	}
//	_MergeSort(a, tmp, 0, n - 1);
//
//	//忘记free
//	free(tmp);
//}

//void MergeSortNoneR(int* a, int n)
//{
//	// 动态分配一个与原数组a大小相同的辅助数组tmp
//	int* tmp = (int*)malloc(sizeof(int) * n);
//	if (tmp == NULL)
//	{
//		// 如果内存分配失败，输出错误信息并退出程序
//		perror("malloc failed");
//		exit(-1);
//	}
//
//	// gap 表示当前每次需要合并的子数组的长度
//	int gap = 1;
//	while (gap < n)
//	{
//		// 遍历数组，每次合并长度为 gap 的相邻子数组
//		for (int i = 0; i < n; i += 2 * gap)
//		{
//			// 初始化子数组的起始和结束索引
//			int begin1 = i;
//			int end1 = i + gap - 1;
//			int begin2 = i + gap;
//			int end2 = i + 2 * gap - 1;
//
//			// 初始化辅助数组的索引
//			int index = i;
//
//			// 如果第二个子数组的起始索引超出数组范围，跳出循环
//			if (begin2 >= n)
//			{
//				break;
//			}
//			// 如果第二个子数组的结束索引超出数组范围，调整结束索引
//			if (end2 >= n)
//			{
//				end2 = n - 1;
//			}
//
//			// 合并两个子数组
//			while (begin1 <= end1 && begin2 <= end2)
//			{
//				if (a[begin1] < a[begin2])
//				{
//					tmp[index++] = a[begin1++];
//				}
//				else
//				{
//					tmp[index++] = a[begin2++];
//				}
//			}
//
//			// 如果第一个子数组还有剩余元素，将其复制到辅助数组
//			while (begin1 <= end1)
//			{
//				tmp[index++] = a[begin1++];
//			}
//
//			// 如果第二个子数组还有剩余元素，将其复制到辅助数组
//			while (begin2 <= end2)
//			{
//				tmp[index++] = a[begin2++];
//			}
//
//			// 将辅助数组tmp中已排序的元素复制回原数组a
//			memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));
//		}
//		// 每次合并完成后，子数组的长度翻倍
//		gap *= 2;
//	}
//
//	// 释放辅助数组的内存
//	free(tmp);
//}

//#include<stdio.h>
//#include<stdlib.h>
//#include<time.h>
//#include<string.h>
//void PrintArray(int* a, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		printf("%d ", a[i]);
//	}
//	printf("\n");
//}
//
//void Swap(int* x, int* y)
//{
//	int tmp = *x;
//	*x = *y;
//	*y = tmp;
//}
//// 时间复杂度O(N*logN)  空间复杂度:O(N)
////递归 归并排序
//void _MergeSort(int* a, int* tmp, int begin, int end)
//{
//	// 递归终止条件：如果开始索引大于或等于结束索引，说明子数组长度为0或1，无需排序，直接返回
//	if (begin >= end)
//		return;
//
//	// 计算中间索引mid
//	int mid = (begin + end) / 2;
//
//	// 递归排序左半部分
//	_MergeSort(a, tmp, begin, mid);
//	// 递归排序右半部分
//	_MergeSort(a, tmp, mid + 1, end);
//
//	// 以下是合并两个已排序的子数组的逻辑
//
//	// 初始化左右子数组的起始和结束索引
//	int begin1 = begin;
//	int end1 = mid;
//	int begin2 = mid + 1;
//	int end2 = end;
//
//	// 初始化辅助数组tmp的索引
//	int index = begin;
//
//	// 合并两个子数组，直到其中一个子数组全部合并完
//	while (begin1 <= end1 && begin2 <= end2)
//	{
//		// 如果左子数组的当前元素小于右子数组的当前元素，则将左子树的当前元素复制到辅助数组中
//		if (a[begin1] < a[begin2])
//		{
//			tmp[index++] = a[begin1++];
//		}
//		// 否则，将右子数组的当前元素复制到辅助数组tmp中
//		else
//		{
//			tmp[index++] = a[begin2++];
//		}
//	}
//
//	// 如果左子数组还有剩余元素，将其全部复制到辅助数组中
//	while (begin1 <= end1)
//	{
//		tmp[index++] = a[begin1++];
//	}
//
//	// 如果右子数组还有剩余元素，将其全部复制到辅助数组中
//	while (begin2 <= end2)
//	{
//		tmp[index++] = a[begin2++];
//	}
//
//	// 将辅助数组tmp中已排序的元素复制回原数组
//	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
//}
//
//void MergeSort(int* a, int n)
//{
//	int* tmp = (int*)malloc(sizeof(int) * n);
//	if (tmp == NULL)
//	{
//		perror("malloc failed");
//		exit(-1);
//	}
//	_MergeSort(a, tmp, 0, n - 1);
//
//	//忘记free
//	free(tmp);
//}
////非递归 归并 排序
//void MergeSortNoneR(int* a, int n)
//{
//	int* tmp = (int*)malloc(sizeof(int) * n);
//	if (tmp == NULL)
//	{
//		perror("malloc failed");
//		exit(-1);
//	}
//
//	int gap = 1;
//	while (gap < n)
//	{
//		for (int i = 0; i < n; i += 2 * gap)
//		{
//			int begin1 = i;
//			int end1 = i + gap - 1;
//			int begin2 = i + gap;
//			int end2 = i + 2 * gap - 1;
//
//			int index = i;
//
//			if (begin2 >= n)
//			{
//				break;
//			}
//			if (end2 >= n)
//			{
//				end2 = n - 1;
//			}
//
//			while (begin1 <= end1 && begin2 <= end2)
//			{
//				if (a[begin1] < a[begin2])
//				{
//					tmp[index++] = a[begin1++];
//				}
//				else
//				{
//					tmp[index++] = a[begin2++];
//				}
//			}
//			while (begin1 <= end1)
//			{
//				tmp[index++] = a[begin1++];
//			}
//			while (begin2 <= end2)
//			{
//				tmp[index++] = a[begin2++];
//			}
//			//memcpy(a + i, tmp + 1, (2 * gap) * sizeof(int));
//			// （i + 2 * gap - 1 ） - i  +1 是错的，因为end2 在下面有可能被修改
//			memcpy(a + i, tmp + 1, (end2 - i + 1) * sizeof(int));
//		}
//		gap *= 2;
//	}
//
//	free(tmp);
//
//}
//void TestOP()
//{
//	srand(time(0));
//	const int N = 10000000;
//	int* a1 = (int*)malloc(sizeof(int) * N);
//	int* a2 = (int*)malloc(sizeof(int) * N);
//
//	for (int i = 0; i < N; i++)
//	{
//		a1[i] = rand() + i;
//		a2[i] = a1[i];
//	}
//	int begin1 = clock();
//	MergeSort(a1, N);
//	int end1 = clock();
//
//	int begin2 = clock();
//	MergeSortNoneR(a2, N);
//	int end2 = clock();
//
//	//PrintArray(a1, N);
//	printf("MergeSort:%d \n", end1 - begin1);
//	printf("MergeSortNoneR:%d \n", end2 - begin2);
//
//	free(a1);
//	free(a2);
//}
//int main()
//{
//
//	TestOP();
//	return 0;
//}
//
//
//void CountSort(int* a, int n)
//{
//    // 初始化最小值和最大值为数组的第一个元素
//    int min = a[0], max = a[0];
//    // 遍历数组以找出最小值和最大值
//    for (int i = 0; i < n; i++)
//    {
//        if (a[i] < min)
//            min = a[i]; // 更新最小值
//        if (a[i] > max)
//            max = a[i]; // 更新最大值
//    }
//
//    // 得到需要创建count数组的个数是range
//    int range = max - min + 1;
//    //创建count数组
//    int* count = (int*)malloc(sizeof(int) * range);
//
//    // 检查内存分配是否成功
//    if (count == NULL)
//    {
//        perror("malloc fail");
//        return;
//    }
//    // 初始化计数数组全为0
//    memset(count, 0, sizeof(int) * range);
//
//    // 统计数据出现次数
//    for (int i = 0; i < n; i++)
//    {
//        // 计算元素在计数数组中的索引，并增加计数
//        count[a[i] - min]++;
//    }
//
//    // 排序数组
//    int j = 0;
//    for (int i = 0; i < range; i++)
//    {
//        // 当计数数组中的计数大于0时，将元素按顺序放回原数组
//        while (count[i]--)
//        {
//            a[j++] = i + min; // 使用min偏移量将计数数组索引映射回原数组元素
//        }
//    }
//
//    // 释放动态分配的计数数组
//    free(count);
//}

//#include<stdio.h>
//#include<stdlib.h>
//
//void CountSort(int* a, int n)
//{
//	int min = a[0], max = a[0];
//	for (int i = 0; i < n; i++)
//	{
//		if (a[i] < min)
//			min = a[i];
//
//		if (a[i] > max)
//			max = a[i];
//	}
//
//	int range2 = max - min + 1;
//	int* count = (int*)malloc(sizeof(int) * range2);
//	printf("range:%d\n", range2);
//	if (count == NULL)
//	{
//		perror("malloc fail");
//		return;
//	}
//	memset(count, 0, sizeof(int) * range2);
//
//	// 统计数据出现次数
//	for (int i = 0; i < n; i++)
//	{
//		count[a[i] - min]++;
//	}
//
//	// 排序
//	int j = 0;
//	for (int i = 0; i < range2; i++)
//	{
//		while (count[i]--)
//		{
//			a[j++] = i + min;
//		}
//	}
//}
//void TestOP()
//{
//	srand(time(0));
//	const int N = 10000000;
//	int* a1 = (int*)malloc(sizeof(int) * N);
//
//	for (int i = N - 1; i >= 0; --i)
//	{
//		a1[i] = rand() + i;
//
//	}
//
//	int begin1 = clock();
//	CountSort(a1, N);
//	int end1 = clock();
//
//	printf("CountSort:%d\n", end1 - begin1);
//
//	free(a1);
//}
//int main()
//{
//	TestOP();
//
//	return 0;
//}
//
////向下调整函数 建立大堆
//void AdjustDown(int* a, int n, int parent)
//{
//	int child = parent * 2 + 1; // 初始化child为parent的左孩子
//	while (child < n) // 当child未越界时循环
//	{
//		if (child + 1 < n && a[child] < a[child + 1]) // 如果右孩子存在且左孩子大于右孩子
//		{
//			child++; // 将child指向右孩子
//		}
//
//		if (a[child] > a[parent]) // 如果孩子节点大于父节点，则违反了大堆的性质
//		{
//			Swap(&a[child], &a[parent]); // 交换孩子节点和父节点的值
//			parent = child; // 更新parent为交换后的位置
//			child = parent * 2 + 1; // 更新child为新的parent的左孩子
//		}
//		else
//		{
//			break; // 如果父节点已经不小于任何一个孩子节点，则调整完毕，退出循环
//		}
//	}
//}
////堆排
//void HeapSort(int* a, int n)
//{
//	for (int i = (n - 2) / 2; i >= 0; i--) // 从最后一个非叶子节点开始，直到根节点
//	{
//		AdjustDown(a, n, i); // 将每个非叶子节点调整为堆的形式
//	}
//	int end = n - 1;
//	while (end > 0) // 当数组还有元素时
//	{
//		Swap(&a[0], &a[end]); // 将堆顶元素（当前最小值）与最后一个元素交换
//		AdjustDown(a, end, 0); // 将剩余的元素重新调整为堆
//		end--; // 减少堆的大小
//	}
//}

//int GetMidi(int* a, int left, int right)
//{
//    // 计算中间元素的下标
//    int mid = (left + right) / 2;
//
//    // 比较三个元素：left, mid, right
//    // 首先比较left和mid
//    if (a[left] < a[mid])
//    {
//        // 如果left < mid，再比较mid和right
//        if (a[mid] < a[right])
//        {
//            // 如果left < mid < right，则mid是中间值
//            return mid;
//        }
//        else if (a[left] > a[right])  // 如果left > right，则mid是最大值
//        {
//            // 在这种情况下，left是中间值
//            return left;
//        }
//        else
//        {
//            // 如果left < right，则right是中间值
//            return right;
//        }
//    }
//    else // 如果a[left] > a[mid]
//    {
//        // 比较mid和right
//        if (a[mid] > a[right])
//        {
//            // 如果mid > right，则mid是中间值
//            return mid;
//        }
//        else if (a[left] < a[right]) // 如果left < right，则mid是最小值
//        {
//            // 在这种情况下，left是中间值
//            return left;
//        }
//        else
//        {
//            // 如果left > right，则right是中间值
//            return right;
//        }
//    }
//}


//int PartSort1(int* a, int left, int right)
//{
//    // 使用三数取中法获取基准元素的正确位置
//    int Mid = GetMidi(a, left, right);
//    // 将基准元素交换到数组的最左边
//    Swap(&a[left], &a[Mid]);
//    // 设置基准元素的索引为keyi
//    int keyi = left;
//
//    // 当left小于right时，进行单趟排序
//    while (left < right)
//    {
//        // 从右向左扫描，找到第一个小于基准元素的值
//        while (left < right && a[right] >= a[keyi])
//        {
//            right--;
//        }
//        // 注意，这里使用&&连接两个条件，并且顺序很重要，
//        // 因为如果left >= right，我们就不再需要继续比较
//        // 此时a[right] >= a[keyi]放在前面的话，会越界访问
//
//        // 从左向右扫描，找到第一个大于基准元素的值
//        while (left < right && a[left] <= a[keyi])
//        {
//            left++;
//        }
//
//        // 交换两个元素，将大于基准的元素放到右边，小于基准的元素放到左边
//        Swap(&a[left], &a[right]);
//    }
//
//    // 最后，将基准元素放到正确的位置（left此时指向的位置）
//    Swap(&a[keyi], &a[left]);
//    // 返回基准元素的最终位置
//    return left;
//}
//
//int PartSort2(int* a, int left, int right)
//{
//    // 使用三数取中法获取基准元素的正确位置
//    int Mid = GetMidi(a, left, right);
//    // 将基准元素交换到数组的最左边
//    Swap(&a[left], &a[Mid]);
//
//    // 把基准值保存到临时变量key中
//    int key = a[left];
//    // 将基准值的下标保存到临时变量hole（坑位）中
//    int hole = left;
//
//    // 当left小于right时，进行单趟排序
//    while (left < right)
//    {
//        // 从右向左扫描，找到第一个小于基准元素的值
//        while (left < right && a[right] >= key)
//        {
//            --right;
//        }
//        // 将找到的元素放到"坑"中
//        a[hole] = a[right];
//        // 更新"坑"的位置
//        hole = right;
//
//        // 从左向右扫描，找到第一个大于基准元素的值
//        while (left < right && a[left] <= key)
//        {
//            ++left;
//        }
//        // 将找到的元素放到"坑"中
//        a[hole] = a[left];
//        // 更新"坑"的位置
//        hole = left;
//    }
//
//    // 最后，将基准元素放到正确的位置（hole此时指向的位置）
//    a[hole] = key;
//    // 返回基准元素的最终位置
//    return hole;
//}

////前后指针法实现
//int PartSort3(int* a, int left, int right)
//{
//	// 1. 获取基准值
//	int midi = GetMidi(a, left, right);
//	// 将基准元素交换到数组的最左边
//	Swap(&a[left], &a[midi]);
//
//	// 2. 初始化指针
//	int prev = left; // 设置前指针prev为起始位置
//	int cur = prev + 1; // 设置后指针cur为起始位置的后一个元素
//
//	// 3. 单趟排序
//	//cur<=right，代表还有元素需要比较
//	while (cur <= right)
//	{
//		// 4. 比较和交换
//		if (a[cur] < a[keyi] && ++prev != cur) //如果后指针cur所指向的元素小于基准值，
//											   //并且prev+1不等于cur才会进行交换
//											   //那么就将prev的后一个（prev+1）和cur进行交换
//		{
//			//交换
//			Swap(&a[prev], &a[cur]);
//
//		}
//
//		// 5. 移动指针
//		++cur; // 继续移动后指针cur
//	}
//
//	// 6. 交换基准值
//	Swap(&a[prev], &a[keyi]);
//
//	// 7. 返回基准值位置
//	return prev;
//}

////递归快排(霍尔)
//void QuickSort1(int* a, int left, int right)
//{
//	if (left >= right)
//		return;
//
//	int keyi = PartSort1(a, left, right);
//
//	QuickSort1(a, left, keyi - 1);
//	QuickSort1(a, keyi + 1, right);
//
//}

////递归快排（挖坑）
//void QuickSort2(int* a, int left, int right)
//{
//	if (left >= right)
//		return;
//
//	int keyi = PartSort2(a, left, right);
//
//	QuickSort2(a, left, keyi - 1);
//	QuickSort2(a, keyi + 1, right);
//
//}

////递归快排（前后指针）
//void QuickSort3(int* a, int left, int right)
//{
//	if (left >= right)
//		return;
//
//	int keyi = PartSort3(a, left, right);
//
//	QuickSort3(a, left, keyi - 1);
//	QuickSort3(a, keyi + 1, right);
//
//}

//void BetterQuickSort(int* a, int left, int right)
//{
//    // 如果left大于或等于right，则数组为空或只有一个元素，无需排序，直接返回
//    if (left >= right)
//        return;
//
//    // 如果数组长度大于10，则使用PartSort1进行快速排序
//    if ((right - left + 1) > 10)
//    {
//        // 调用PartSort1函数获取基准值的位置
//        int keyi = PartSort1(a, left, right);
//
//        // 对基准值左边的部分进行快速排序
//        QuickSort1(a, left, keyi - 1);
//
//        // 对基准值右边的部分进行快速排序
//        QuickSort1(a, keyi + 1, right);
//    }
//    // 如果数组长度小于或等于10，则使用插入排序
//    else
//    {
//        // 对left到right之间的部分进行插入排序
//        InsertSort(a + left, right - left + 1);
//    }
//}

//void  QuickSortNoneR(int* a, int left, int right)
//{
//    // 1. 初始化栈
//    ST st;
//    STInit(&st);
//
//    // 2. 入栈：将right和left的值分别入栈
//    STPush(&st, right);
//    STPush(&st, left);
//
//    // 3. 栈不为空时继续处理
//    while (!STEmpty(&st))
//    {
//        // 4. 出栈：从栈顶取出begin和end的值
//        int begin = STTop(&st);
//        STPop(&st);
//        int end = STTop(&st);
//        STPop(&st);
//
//        // 5. 调用PartSort1函数获取基准值的位置
//        int keyi = PartSort1(a, begin, end);
//
//        // 6. 入栈：根据keyi的位置，将右半部分和左半部分的起始位置入栈
//        if (keyi + 1 < end)
//        {
//            STPush(&st, end);
//            STPush(&st, keyi + 1);
//        }
//
//        if (keyi - 1 > begin)
//        {
//            STPush(&st, keyi - 1);
//            STPush(&st, begin);
//        }
//    }
//
//    // 7. 销毁栈
//    STDestroy(&st);
//}

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include "Stack.h"
//插入函数
void InsertSort(int* arr, int N)
{
	for (int i = 0; i < N - 1; i++)
	{
		int end = i;
		//即将排序的元素，保留在tmp
		int tmp = arr[end + 1];
		//end>=0代表还有元素未比较
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		//来到这里分为两种情况 
		//1：break->遇到比元素tmp小或和tmp相等的，将m放在它的后面
		//2：全部比较完了，都没有遇到<=tmp的，最后tmp放在数组第一个位置
		arr[end + 1] = tmp;
	}

}
//交换
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
//三数取中
int GetMidi(int* a, int left, int right)
{
	// 计算中间元素的下标
	int mid = (left + right) / 2;

	// 比较三个元素：left, mid, right
	// 首先比较left和mid
	if (a[left] < a[mid])
	{
		// 如果left < mid，再比较mid和right
		if (a[mid] < a[right])
		{
			// 如果left < mid < right，则mid是中间值
			return mid;
		}
		else if (a[left] > a[right])  // 如果left > right，则mid是最大值
		{
			// 在这种情况下，left是中间值
			return left;
		}
		else
		{
			// 如果left < right，则right是中间值
			return right;
		}
	}
	else // 如果a[left] > a[mid]
	{
		// 比较mid和right
		if (a[mid] > a[right])
		{
			// 如果mid > right，则mid是中间值
			return mid;
		}
		else if (a[left] < a[right]) // 如果left < right，则mid是最小值
		{
			// 在这种情况下，left是中间值
			return left;
		}
		else
		{
			// 如果left > right，则right是中间值
			return right;
		}
	}
}
//全部忘加[],第二个写成if

//第一种单趟：霍尔法
int PartSort1(int* a, int left, int right)
{
	// 使用三数取中法获取基准元素的正确位置
	int Mid = GetMidi(a, left, right);
	// 将基准元素交换到数组的最左边
	Swap(&a[left], &a[Mid]);
	// 设置基准元素的索引为keyi
	int keyi = left;

	// 当left小于right时，进行单趟排序
	while (left < right)
	{
		// 从右向左扫描，找到第一个小于基准元素的值
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		// 注意，这里使用&&连接两个条件，并且顺序很重要，
		// 因为如果left >= right，我们就不再需要继续比较
		// 此时a[right] >= a[keyi]放在前面的话，会越界访问

		// 从左向右扫描，找到第一个大于基准元素的值
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		// 交换两个元素，将大于基准的元素放到右边，小于基准的元素放到左边
		Swap(&a[left], &a[right]);
	}

	// 最后，将基准元素放到正确的位置（left此时指向的位置）
	Swap(&a[keyi], &a[left]);
	// 返回基准元素的最终位置
	return left;
}
//挖坑法
int PartSort2(int* a, int left, int right)
{
	// 使用三数取中法获取基准元素的正确位置
	int Mid = GetMidi(a, left, right);
	// 将基准元素交换到数组的最左边
	Swap(&a[left], &a[Mid]);

	// 设置基准元素的值
	int key = a[left];
	// 设置基准元素的位置
	int hole = left;

	// 当left小于right时，进行单趟排序
	while (left < right)
	{
		// 从右向左扫描，找到第一个小于基准元素的值
		while (left < right && a[right] >= key)
		{
			--right;
		}
		// 将找到的元素放到"坑"中
		a[hole] = a[right];
		// 更新"坑"的位置
		hole = right;

		// 从左向右扫描，找到第一个大于基准元素的值
		while (left < right && a[left] <= key)
		{
			++left;
		}
		// 将找到的元素放到"坑"中
		a[hole] = a[left];
		// 更新"坑"的位置
		hole = left;
	}

	// 最后，将基准元素放到正确的位置（hole此时指向的位置）
	a[hole] = key;
	// 返回基准元素的最终位置
	return hole;
}
前后指针法
//int partsort3(int* a, int left, int right)
//{
//	int prev = left;
//	int cur = left + 1;
//
//	while (cur <= right)
//	{
//		if (a[cur] < a[left] && ++prev != cur)
//		{
//			Swap(&a[cur], &a[prev]);
//
//		}
//		cur++;
//	}
//	Swap(&a[prev], &a[left]);
//	//最后比left元素小的 都集中在了prev的下面及其左面，此时prev和left交换，最左面的元素一定是来到了正确的位置
//	return prev;
//	//a[cur] < a[left] 后 cur肯定是要++的，
//	//如果此时prev+1 = cur就代表prev和cur之间还没有比下标为left的元素大的元素，所以没必要交换，
//	//当++prev!=cur 的时候才交换，其次++prev!=cur 不仅判断还+1了，
//}
//第三种单趟：前后指针法
//int  partsort3(int* a, int left, int right)
//{
//	int Mid = GetMidi(a, left, right);
//	Swap(&a[left], &a[Mid]);
//
//	int prev = left;
//	int cur = prev + 1;
//	int keyi = left;
//
//	while (cur <= right)
//	{
//		if (a[cur] < a[keyi] && ++prev != cur)
//		{
//			Swap(&a[cur], &a[prev]);
//
//		}
//		cur++;
//	}
//	Swap(&a[prev], &a[keyi]);
//	return prev;
//}
////前后指针法
//int PartSort3(int* a, int left, int right)
//{
//	// 1. 获取基准值
//	int midi = GetMidi(a, left, right);
//	// 将基准值与数组的第一个元素交换，确保基准值位于起始位置
//	Swap(&a[left], &a[midi]);
//
//	// 2. 初始化指针
//	int prev = left; // 设置前指针prev为起始位置
//	int cur = prev + 1; // 设置后指针cur为起始位置的后一个元素
//
//	int keyi = left;
//
//	// 3. 单趟排序
//	while (cur <= right)
//	{
//		// 4. 比较和交换
//		if (a[cur] < a[keyi] && ++prev != cur) // 如果后指针cur所指向的元素小于基准值
//		{
//			Swap(&a[prev], &a[cur]); // 并且前指针prev还没有到达cur的位置，
//			// 则将前指针向前移动一位，并与后指针指向的元素交换
//		}
//
//		// 5. 移动指针
//		++cur; // 继续移动后指针cur
//	}
//
//	// 6. 交换基准值
//	Swap(&a[prev], &a[keyi]);
//
//	// 7. 返回基准值位置
//	return prev;
//}
//
//
//// 交换两个元素
//void Swap(int* x, int* y)
//{
//	int temp = *x;
//	*x = *y;
//	*y = temp;
//}
////递归快排(霍尔)
//void QuickSort1(int* a, int left, int right)
//{
//	if (left >= right)
//		return;
//
//	int keyi = PartSort1(a, left, right);
//
//	QuickSort1(a, left, keyi - 1);
//	QuickSort1(a, keyi + 1, right);
//
//}
////递归快排（挖坑）
//void QuickSort2(int* a, int left, int right)
//{
//	if (left >= right)
//		return;
//
//	int keyi = PartSort2(a, left, right);
//
//	QuickSort2(a, left, keyi - 1);
//	QuickSort2(a, keyi + 1, right);
//
//}
////递归快排（前后指针）
//void QuickSort3(int* a, int left, int right)
//{
//	if (left >= right)
//		return;
//
//	int keyi = PartSort3(a, left, right);
//
//	QuickSort3(a, left, keyi - 1);
//	QuickSort3(a, keyi + 1, right);
//
//}
////优化递归快排
//void BetterQuickSort(int* a, int left, int right)
//{
//	if (left >= right)
//		return;
//
//	if ((right - left + 1) > 10)
//	{
//		int keyi = PartSort1(a, left, right);
//
//		QuickSort1(a, left, keyi - 1);
//		QuickSort1(a, keyi + 1, right);
//
//	}
//	else
//	{
//		InsertSort(a + left, right - left + 1);
//	}
//	//左面确认起点，右面确认个数
//}
////非递归快排，借助栈
//void  QuickSortNoneR(int* a, int left, int right)
//{
//	// 1. 初始化栈
//	ST st;
//	STInit(&st);
//
//	// 2. 入栈：将right和left的值分别入栈
//	STPush(&st, right);
//	STPush(&st, left);
//
//	// 3. 栈不为空时继续处理
//	while (!STEmpty(&st))
//	{
//		// 4. 出栈：从栈顶取出begin和end的值
//		int begin = STTop(&st);
//		STPop(&st);
//		int end = STTop(&st);
//		STPop(&st);
//
//		// 5. 调用PartSort1函数获取基准值的位置
//		int keyi = PartSort1(a, begin, end);
//
//		// 6. 入栈：根据keyi的位置，将右半部分和左半部分的起始位置入栈
//		if (keyi + 1 < end)
//		{
//			STPush(&st, end);
//			STPush(&st, keyi + 1);
//		}
//
//		if (keyi - 1 > begin)
//		{
//			STPush(&st, keyi - 1);
//			STPush(&st, begin);
//		}
//	}
//
//	// 7. 销毁栈
//	STDestroy(&st);
//}
////非递归快排(借助栈)
////void QuickSortNoneR(int* a, int begin, int end)
////{
////	ST st;
////	STInit(&st);
////	STPush(&st, end);
////	STPush(&st, begin);
////	while (!STEmpty(&st))
////	{
////		int left = STTop(&st);
////		STPop(&st);
////
////		int right = STTop(&st);
////		STPop(&st);
////
////		int keyi = PartSort1(a, left, right);
////		// [lefy,keyi-1] keyi [keyi+1, right]
////		if (keyi + 1 < right)
////		{
////			STPush(&st, right);
////			STPush(&st, keyi + 1);
////		}
////
////		if (left < keyi - 1)
////		{
////			STPush(&st, keyi - 1);
////			STPush(&st, left);
////		}
////	}
////
////	STDestroy(&st);
////}
////测试少量快排
//void Test1()
//{
//	int a[] = { 6,1,2,7,9,3,4,5,10,8 };
//	QuickSortNoneR(a, 0, sizeof(a) / sizeof(int) - 1);
//	PrintArray(a, sizeof(a) / sizeof(int));
//}
////测试大量快排
//void Test2()
//{
//
//	srand(time(0));
//	int N = 10000000;
//	int* a1 = (int*)malloc(sizeof(int) * N);
//
//	for (int i = N - 1; i >= 0; --i)
//	{
//		a1[i] = rand() + i;
//	}
//
//	int begin1 = clock();
//	QuickSort1(a1, 0, N - 1);
//	int end1 = clock();
//
//	printf("QuickSort1:%d\n", end1 - begin1);
//
//	free(a1);
//}
////测试优化递归后的大量快排
//void Test3()
//{
//	srand(time(0));
//	int N = 10000000;
//	int* a1 = (int*)malloc(sizeof(int) * N);
//
//	for (int i = N - 1; i >= 0; --i)
//	{
//		a1[i] = rand() + i;
//	}
//
//	int begin1 = clock();
//	BetterQuickSort(a1, 0, N - 1);
//	int end1 = clock();
//
//	printf("BetterQuickSort:%d\n", end1 - begin1);
//
//	free(a1);
//
//}
////测试非递归快排
//void Test4()
//{
//	srand(time(0));
//	int N = 10000000;
//	int* a1 = (int*)malloc(sizeof(int) * N);
//
//	for (int i = N - 1; i >= 0; --i)
//	{
//		a1[i] = rand() + i;
//	}
//
//	int begin1 = clock();
//	QuickSortNoneR(a1, 0, N - 1);
//	int end1 = clock();
//
//	printf("QuickSortNoneR:%d\n", end1 - begin1);
//
//	free(a1);
//}
//int main()
//{
//	//测试递归少量快排
//	Test1();
//	//测试递归大量快排
//	Test2();
//	//测试优化递归大量快排
//	Test3();
//	//测试非递归大量快排
//	Test4();
//
//	return 0;
//}
